package LeetCode._03_链表;


import java.util.ArrayList;

public class _11扁平化多级双向链表 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }
    public Node flatten(Node head) {
        if(head == null) return null;
        ArrayList<Node> list = new ArrayList<>();
        Node tmp = head;
        inorder(tmp,list);
        if(list.size() > 0){
            for (Node node : list) {
                node.prev = tmp;
                node.next = null;
                node.child = null;
                tmp.next = node;
                tmp = node;
            }
        }
        head.prev = null;
        head.child = null;
        return head;
    }

    //利用树的先序遍历将每个节点装进集合
    public void inorder(Node head, ArrayList<Node> list){
        if(head != null){
            list.add(head);
            inorder(head.child,list);
            inorder(head.next,list);
        }
    }
}
